package LeetCode_101_200;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution128 {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int maxLength = 0;
        for (int num : numSet) {
            // 只有当num是序列起点（前驱不存在）时才处理
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;

                // 向后扩展序列
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }
                maxLength = Math.max(maxLength, currentLength);
            }
        }
        return maxLength;
    }
}

public class LeetCode128_longestConsecutive {
    public static void main(String[] args) {
        Solution128 solution = new Solution128();
        int[] nums1 = new int[] {100,4,200,1,3,2};
        int[] nums2 = new int[] {0,3,7,2,5,8,4,6,0,1};
        int[] nums3 = new int[] {1,0,1,2};
        System.out.println(Arrays.toString(nums1));
        System.out.println(solution.longestConsecutive(nums1));
        System.out.println(Arrays.toString(nums2));
        System.out.println(solution.longestConsecutive(nums2));
        System.out.println(Arrays.toString(nums3));
        System.out.println(solution.longestConsecutive(nums3));

    }
}
